#include <vector>
#include <string>
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

class Code03_DecodeWays
{
public:
    // 暴力尝试
    static int numDecodings1(string s)
    {
        return f1(s, 0);
    }

    // s : 数字字符串
    // s[i....]有多少种有效的转化方案
    static int f1(const string &s, int i)
    {
        if (i == s.length())
        {
            return 1;
        }
        int ans;
        if (s[i] == '0')
        {
            ans = 0;
        }
        else
        {
            ans = f1(s, i + 1);
            if (i + 1 < s.length() && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26)
            {
                ans += f1(s, i + 2);
            }
        }
        return ans;
    }

    // 暴力尝试改记忆化搜索
    static int numDecodings2(string s)
    {
        vector<int> dp(s.length(), -1);
        return f2(s, 0, dp);
    }

    static int f2(const string &s, int i, vector<int> &dp)
    {
        if (i == s.length())
        {
            return 1;
        }
        if (dp[i] != -1)
        {
            return dp[i];
        }
        int ans;
        if (s[i] == '0')
        {
            ans = 0;
        }
        else
        {
            ans = f2(s, i + 1, dp);
            if (i + 1 < s.length() && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26)
            {
                ans += f2(s, i + 2, dp);
            }
        }
        dp[i] = ans;
        return ans;
    }

    // 严格位置依赖的动态规划
    static int numDecodings3(string s)
    {
        int n = s.length();
        vector<int> dp(n + 1, 0);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == '0')
            {
                dp[i] = 0;
            }
            else
            {
                dp[i] = dp[i + 1];
                if (i + 1 < s.length() && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26)
                {
                    dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }

    // 严格位置依赖的动态规划 + 空间压缩
    static int numDecodings4(string s)
    {
        // dp[i+1]
        int next = 1;
        // dp[i+2]
        int nextNext = 0;
        for (int i = s.length() - 1, cur; i >= 0; i--)
        {
            if (s[i] == '0')
            {
                cur = 0;
            }
            else
            {
                cur = next;
                if (i + 1 < s.length() && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26)
                {
                    cur += nextNext;
                }
            }
            nextNext = next;
            next = cur;
        }
        return next;
    }
};
int main()
{
    string s = "226";

    int result1 = Code03_DecodeWays::numDecodings1(s);
    int result2 = Code03_DecodeWays::numDecodings2(s);
    int result3 = Code03_DecodeWays::numDecodings3(s);
    int result4 = Code03_DecodeWays::numDecodings4(s);

    // 输出结果
    cout << "Result 1: " << result1 << endl;
    cout << "Result 2: " << result2 << endl;
    cout << "Result 3: " << result3 << endl;
    cout << "Result 4: " << result4 << endl;

    return 0;
}
